package stu.day50;

import java.util.*;

public class hw2 {


    boolean flag = true;


    public int[] findRedundantConnection(int[][] edges) {

        int n = edges.length;
        Map<Integer, List<Integer>> map = new HashMap<>();

        for(int i=0;i<n;i++){
            map.put(i,new ArrayList<Integer>());
        }

        flag = true;
        for (int[] arr:edges){

            boolean[] vst = new boolean[n];
            Arrays.fill(vst,false);

            dfs(map,vst,arr[0],arr[1]);
            if(!flag){
                return arr;
            }
            map.get(arr[0]).add(arr[1]);
            map.get(arr[1]).add(arr[0]);


        }

        return new int[]{};

    }

    public void dfs(Map<Integer, List<Integer>> map, boolean[] vst, int begin,int end){
        if(vst[begin]) return;

        vst[begin] = true;
        if(begin==end){
            flag = false;
            return;
        }
        for (Integer x:map.get(begin)){
            dfs(map,vst,x,end);
        }
    }



}
